package LeetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}20:32
 */
public class LeetCode3 {
//    public int lengthOfLongestSubstring(String s) {
//        if (s.equals("")){
//            return 0;
//        }
//        char[] arr = s.toCharArray();
//        //滑动窗口
//        int i = 0;
//        int j = 0;
//        int maxSize = 0;
//        Set<Character> set = new HashSet<>();
//        while (j < arr.length  && i < arr.length){
//            if (!set.contains(arr[j])){
//                set.add(arr[j++]);
//                maxSize = Math.max(j - i,maxSize);
//            }else {
//                set.remove(arr[i++]);
//            }
//        }
//        return maxSize;
//    }
    public static void main(String[] args) {

        System.out.println(new LeetCode3().lengthOfLongestSubstring("abcabcbb"));
    }

    //暴力解法
//    public int lengthOfLongestSubstring(String s) {
//        int n = s.length(), ans = 0;
//        Map<Character, Integer> map = new HashMap<>(); // current index of character
//        // try to extend the range [i, j]
//        for (int j = 0, i = 0; j < n; j++) {
//            if (map.containsKey(s.charAt(j))) {
//                i = Math.max(map.get(s.charAt(j)), i);
//            }
//            ans = Math.max(ans, j - i + 1);
//            map.put(s.charAt(j), j + 1);
//        }
//        return ans;
//    }

    //滑动窗口
    public int lengthOfLongestSubstring(String s){
        int[] freq = new int[256];//出现频率 因为字母ASCLL码顶天256
        // 滑动窗口的指针
        int l = 0;
        int r = -1;
        int res = 0;

        while (l < s.length()){
            if (r + 1 < s.length() && freq[s.charAt(r+1)] == 0){
                freq[s.charAt(++r)]++;
            }else {
                freq[s.charAt(l++)]--;// 左指针移动
            }
            res = Math.max(res,r-l+1);
        }
        return res;
    }
}
